package com.leetcode.根据数据结构分类.并查集;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: ZhouBert
 * @date: 2021/1/11
 * @description: 1202. 交换字符串中的元素
 * https://leetcode-cn.com/problems/smallest-string-with-swaps/
 * 感觉起来，评价为 中等题目的原因：在于集成了多个算法的应用题！
 */
public class B_1202_交换字符串中的元素 {

	//位置的索引
	public int[] parents;

	/**
	 * 目的：达到按照最小字典顺序（从题目中可以发现允许重复）
	 * １.并查集找到集合；
	 * 2.根据不同的集合分别进行排序
	 * --
	 * 优化方向（虽然思路是对的，但是耗时 400+ ms 实在是太慢了）：
	 * 1.在 map 中不应该存 value = List<位置>，而是直接存 List<位置对应的 char >,然后每一次从 list 获取最小即可
	 * （可以利用小顶堆实现！）
	 *
	 * @param s
	 * @param pairs
	 * @return
	 */
	public String smallestStringWithSwaps4Mine(String s, List<List<Integer>> pairs) {
		int len = s.length();
		if (len == 1) {
			return s;
		}
		InnerUnionFind2 unionFind = new InnerUnionFind2(s.length());
		for (int i = 0; i < pairs.size(); i++) {
			unionFind.union(pairs.get(i).get(0), pairs.get(i).get(1));
		}
		//遍历并查集，去组装 map
		HashMap<Integer, List<Integer>> map = new HashMap<>();

		//遍历一遍做一次 Path Compression
		//-> 通过 UnionFind 获取，这样可以节省 O(n)
		//但是效果依然不明显，还是用  二叉堆比较快！
//		for (int i = 0; i < parents.length; i++) {
//			unionFind.find(i);
//		}
		for (int i = 0; i < len; i++) {
			int root = unionFind.find(i);
			if (map.containsKey(root)) {
				map.get(root).add(i);
			} else {
				List<Integer> tmpList = new ArrayList<>();
				tmpList.add(i);
				map.put(root, tmpList);
			}
		}

		char[] chars = s.toCharArray();
		//针对 map 进行排序
		for (Map.Entry<Integer, List<Integer>> item :
				map.entrySet()) {
			order(chars, item.getValue(), 0, item.getValue().size());
		}

		return new String(chars);
	}

	/**
	 * 针对 list 对 str 进行快速排序
	 * [)
	 *
	 * @param list  位置索引列表
	 * @param chars 待排序的
	 * @return
	 */
	private void order(char[] chars, List<Integer> list, int begin, int end) {
		int b = begin;
		int e = end;
		//位置
		int pivot = list.get(begin);
		char pivotValue = chars[pivot];
		end--;
		while (begin < end) {
			while (begin < end && chars[list.get(end)] >= pivotValue) {
				//从 end 找到比 pivot 位置的 char 小
				end--;
			}
			//此时 find or begin == end
			if (begin == end) {
				break;
			} else {
				//cover begin
				chars[list.get(begin)] = chars[list.get(end)];
				begin++;
			}
			while (begin < end && chars[list.get(begin)] <= pivotValue) {
				begin++;
			}
			if (begin == end) {
				break;
			} else {
				//cover end
				chars[list.get(end)] = chars[list.get(begin)];
				end--;
			}
		}
		chars[list.get(begin)] = pivotValue;

		if (b < begin - 1) {
			order(chars, list, b, begin);
		}
		if (begin + 1< e - 1) {
			//pivot 的位置已经不需要参与排序了！
			order(chars, list, begin + 1, e);
		}


	}

	class InnerUnionFind2 {


		/**
		 * constructor
		 *
		 * @param capacity
		 */
		public InnerUnionFind2(int capacity) {
			parents = new int[capacity];
			for (int i = 0; i < parents.length; i++) {
				parents[i] = i;
			}
		}

		/**
		 * 合并
		 *
		 * @param index1
		 * @param index2
		 */
		public void union(Integer index1, Integer index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			//直接将 p1 的根节点嫁接到 p2 的根节点
			parents[p1] = p2;
		}

		/**
		 * 找到数组中 index 索引下的根节点
		 *
		 * @param index
		 * @return
		 */
		public int find(int index) {
			int root = index;
			while (root != parents[root]) {
				root = parents[root];
			}
			//此时找到 根节点
			//再去遍历路径中的节点，将所有节点的根节点改为 root
			//进行 Path Compression
			int cur = index;
			int prev = cur;
			while (cur != parents[cur]) {
				prev = parents[cur];
				//1.修复
				parents[cur] = root;
				//2.继续往上遍历
				cur = parents[prev];
			}
			return root;
		}
	}

	class InnerUnionFind {
		//index
		//int[] parents;
		private int[] rank;

		public InnerUnionFind(int capacity) {
			parents = new int[capacity];
			this.rank = new int[capacity];
			for (int i = 0; i < capacity; i++) {
				parents[i] = i;
				this.rank[i] = 1;
			}
		}

		/**
		 * 在并查集中查找 index 下的根节点，并做 Path Compression
		 *
		 * @param index
		 * @return
		 */
		public int find(int index) {
			if (index != parents[index]) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}

		/**
		 * @param index1
		 * @param index2
		 */
		public void union(Integer index1, Integer index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			//否则挂在 p2 上
//			parents[p1] = p2;

			if (rank[p1] == rank[p2]) {
				parents[p1] = p2;
				// 此时以 rootY 为根结点的树的高度仅加了 1
				rank[p2]++;
			} else if (rank[p1] < rank[p2]) {
				parents[p1] = p2;
				// 此时以 rootY 为根结点的树的高度不变
			} else {
				// 同理，此时以 rootX 为根结点的树的高度不变
				parents[p2] = p1;
			}
		}
	}

	public static void main(String[] args) {
		String s = "dcab";
		List<List<Integer>> pairs = new ArrayList<>();
		List<Integer> t1 = new ArrayList<>();
		List<Integer> t2 = new ArrayList<>();
		List<Integer> t3 = new ArrayList<>();
		t1.add(0);
		t1.add(3);
		t2.add(1);
		t2.add(2);
		t3.add(0);
		t3.add(2);
		pairs.add(t1);
		pairs.add(t2);
		pairs.add(t3);

		B_1202_交换字符串中的元素 action = new B_1202_交换字符串中的元素();
		String res = action.smallestStringWithSwaps4Mine(s, pairs);
		System.out.println("res = " + res);
	}
}
